#include "seq-list.cpp"

/***
 * 归并排序
 * 基本思路: 采用分治策略, 将序列递归分成小序列, 排序后合并为有序大序列
 * 时间复杂度: 平均O(nlogn) 最好O(nlogn) 最坏O(nlogn)
 * 空间复杂度: O(n)
 * 稳定性: 稳定
 * */

void merge(SqList &L, int low, int mid, int high) {
    // 合并例如: 3 5 6 | 2 3 7 -> 2 3 3 5 6 7
    // low-mid mid+1-high
    int i = low, j = mid+1;
    int index = 0;
    int temp[high-low+1];
    while (i <= mid && j <= high)
    {
        if (L.data[i] <= L.data[j])
            temp[index++] = L.data[i++];
        else
            temp[index++] = L.data[j++];
    }

    while (i <= mid)
    {
        temp[index++] = L.data[i++];
    }
    
    while (j <= high)
    {
        temp[index++] = L.data[j++];
    }
    
    index = 0;
    while (low <= high)
    {
        L.data[low++] = temp[index++];
    }    
}

void mergeSort(SqList &L, int low, int high)
{
    if (low < high) {
        // 取中间下标
        int mid = (low + high) / 2;
        mergeSort(L, low, mid);
        mergeSort(L, mid+1, high);
        merge(L, low, mid, high);
    }
}

void sort(SqList &L)
{
    mergeSort(L, 0, L.length - 1);
}

int main(int argc, char const *argv[])
{
    SqList L;
    int data[6] = {6, 5, 3, 2, 7, 1};
    L.data = data;
    L.length = 6;
    printList(L);
    sort(L);
    printList(L);
    return 0;
}
